package leetcode_901_1000;

import java.util.Arrays;

public class LeeCode_1001 {
    public static void main(String[] args) {
        System.out.println(mergeStones(new int[]{3, 2, 4, 1}, 2));
        System.out.println(mergeStones(new int[]{3, 2, 4, 1}, 3));
        System.out.println(mergeStones(new int[]{3, 5,1,2,6}, 3));
    }
    private static int mergeStones(int[] stones, int k) {
        int n = stones.length;
        if ((n - 1) % (k - 1) != 0)
            return -1;
        int[][][] memo = new int[n][n][k + 1];
        int[] s = new int[n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                Arrays.fill(memo[i][j], -1);
            }
        }
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + stones[i];
        }
        return dfs(0, n - 1, 1, memo, s, k);
    }
    private static int dfs(int i, int j, int p, int[][][] memo, int[] s, int k){
        if (memo[i][j][p] != -1)
            return memo[i][j][p];
        if (p == 1)
            return memo[i][j][p] = i == j ? 0 : dfs(i, j, k, memo, s, k) + s[j + 1] - s[i];
        int res = Integer.MAX_VALUE;
        for (int m = i; m < j; m += k - 1) {
            res = Math.min(res, dfs(i, m, 1, memo, s, k) + dfs(m + 1, j, p - 1, memo, s, k));
        }
        return memo[i][j][p] = res;
    }
}
